package com.javabasic.algorithm.sword_of_offer;

import java.util.Stack;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see
 * @since Created by work on 2022/1/5 9:27 下午
 */
public class 剑指_Offer_09_用两个栈实现队列 {

}

/**
 * 暴力解法，在两个stack中来回颠倒
 */
class CQueue {
    Stack<Integer> stack1;
    Stack<Integer> stack2;

    public CQueue() {
        stack1 = new Stack<Integer>();
        stack2 = new Stack<Integer>();
    }

    public void appendTail(int value) {
        stack1.push(value);
    }

    public int deleteHead() {
        if (stack1.empty()) {
            return -1;
        }
        while (!stack1.empty()) {
            stack2.push(stack1.pop());
        }
        Integer result = stack2.pop();
        while (!stack2.empty()) {
            stack1.push(stack2.pop());
        }
        return result;
    }
}


/**
 * 暴力解法优化，类似懒加载机制
 */
class CQueue2 {
    Stack<Integer> stack1;
    Stack<Integer> stack2;

    public CQueue2() {
        stack1 = new Stack<Integer>();
        stack2 = new Stack<Integer>();
    }

    public void appendTail(int value) {
        while (!stack2.empty()) {
            stack1.push(stack2.pop());
        }
        stack1.push(value);
    }

    public int deleteHead() {
        if (!stack2.empty()) {
            return stack2.pop();
        }
        if (stack1.empty()) {
            return -1;
        }
        while (!stack1.empty()) {
            stack2.push(stack1.pop());
        }
        Integer result = stack2.pop();
        return result;
    }
}
